// var topKFrequent = function(nums, k) {
//     const map = new Map()
//     nums.forEach(num => {
//         map.set(num, map.has(num) ? map.get(num) + 1 : 1)
//     })
//     const arr = Array.from(map).sort((a,b) => b[1] - a[1])
//     return arr.slice(0,k).map(item => item[0])
// };

class MinHeap {
    constructor(props) {
        super(props);
        this.heap = []
    }

    swap (i1, i2) {
        const temp = this.heap[i1]
        this.heap[i1] = this.heap[i2]
        this.heap[i2] = temp
    }

    getParentIndex(index) {
        return (index - 1) >> 1
    }

    shiftUp(index) {
        if (index === 0) return
        const parentIndex = this.getParentIndex(index)
        if (this.heap[parentIndex] && this.heap[parentIndex].value > this.heap[index].value) {
            this.swap(parentIndex, index)
            this.shiftUp(parentIndex)
        }
    }

    getLeftChild(index) {
        return 2 * index + 1
    }

    getRightChild(index) {
        return 2 * index + 2
    }
    
    insert(value) {
        this.heap.push(value)
        this.shiftUp(this.heap.length - 1)
    }

    shiftDown (index) {
        const leftIndex = this.getLeftChild(index)
        const rightIndex = this.getRightChild(index)
        if (this.heap[leftIndex] && this.heap[leftIndex].value < this.heap[index].value) {
            this.swap(leftIndex, index)
            this.shiftDown(leftIndex)
        }
        if (this.heap[rightIndex] && this.heap[rightIndex].value < this.heap[index].value) {
            this.swap(rightIndex, index)
            this.shiftDown(rightIndex)
        }
    }

    pop() {
        this.heap[0] = this.heap.pop()
        this.shiftDown(0)
    }

    getHeapTop() {
        return this.heap[0]
    }

    getHeapSize() {
        return this.heap.length
    }
}

var topKFrequent = function(nums, k) {
    const map = new Map()
    nums.forEach(num => {
        map.set(num, map.has(num) ? map.get(num) + 1 : 1)
    })
    const heap = new MinHeap()
    map.forEach((value, key) => {
        heap.insert({value, key})
        if (heap.getHeapSize() > k) {
            heap.pop()
        }
    })
    return heap.map(item => item.key)
};
